package com.hdu.other.monotonyStack;


public class lc1504 {
    class Solution {
        public int numSubmat(int[][] mat) {
            int colLen = mat[0].length;
            int[] heights = new int[colLen];

            int ans = 0;
            for (int i = 0; i < mat.length; i++) {
                for (int j = 0; j < colLen; j++) {
                    heights[j] = mat[i][j] == 0 ? 0 : heights[j] + 1;
                }
                ans += cal(heights);
            }

            return ans;
        }


        int cal(int[] heights) {
            int n = heights.length;
            int[] stack = new int[n];
            int r = 0;
            int ans = 0;
            for (int i = 0; i < n; i++) {
                if (r == 0 || heights[i] > heights[stack[r - 1]]) stack[r++] = i;
                else {
                    while (r > 0 && heights[i] <= heights[stack[r - 1]]) {
                        int index = stack[--r];
                        int left = r == 0 ? -1 : stack[r - 1];
                        int curLen = (i - 1) - (left + 1) + 1;
                        int bottom = Math.max(
                                left == -1 ? 0 : heights[left],
                                heights[i]
                        );
                        int heightLen = heights[index] - bottom;
                        ans += ((curLen + 1) * curLen / 2) * heightLen;
                    }
                    stack[r++] = i;
                }
            }


            while (r > 0) {
                int index = stack[--r];
                int left = r == 0 ? -1 : stack[r - 1];
                int curLen = (n - 1) - (left + 1) + 1;
                int bottom = Math.max(
                        left == -1 ? 0 : heights[left],
                        0
                );
                int heightLen = heights[index] - bottom;
                ans += ((curLen + 1) * curLen / 2) * heightLen;
            }

            return ans;
        }
    }
}
